A primary concern of businesses with mission critical computing is quality of service or the ability to manage computing resources so as to minimize response times and maximize throughputs. Constrained optimization techniques are widely used in computing systems for optimal resource allocation, such as allocating servers in a server farm to improve system throughputs or adjusting the size of memory pools to reduce delays in a database management system.
Generally, constrained optimization has been implemented using techniques such as constraint programming (D. G. Luenberger, Linear and Nonlinear Programming, Addison-Wesley, Reading, Mass., 1984), genetic algorithms (T. L. Lau, et al., The Guided Genetic Algorithm and its Application to the Generalized Assignment Problem, Proceedings of the Tenth IEEE International Conference on Tools with Artificial Intelligence, Taipei, Taiwan, pp. 336-343, 1998), and heuristic search (P. Dasgupta, et al., Solving Constraint Optimization Problems from CLP-style Specifications Using Heuristic Search Techniques, IEEE Transactions on Knowledge and Data Engineering, pp. 353-368, 2002).
Unfortunately, none of the above approaches takes into consideration the dynamics of computing systems such as the delay of control actions of adjusting configuration parameters, and the overheads of adjusting these configuration parameters (i.e., the cost of control actions). With the growth of the Internet, the dynamics of on-demand computing systems have become increasingly important, especially with respect to “flash events” that can cause very rapid, dramatic changes in workloads, requiring prompt control actions which result in control delay and control costs that are not negligible.
On the other hand, the control literature contains extensive studies of dynamic systems with constraints in which optimization is performed (see, e.g., M. Athans, et al., Optimal Control: An Introduction to the Theory and its Applications, McGraw-Hill Book Company, New York, 1966; S. Lyashevskiy, Control of linear dynamic systems with constraints: optimization issues and applications of nonquadratic functionals, Proceedings of the 35th IEEE Conference on Decision and Control, Kobe, Japan, pp. 3206-3211, 1996; A. S. Matveev, Application of linear-quadratic control theory to the solution of special nonconvex problems of global constrained optimization, Proceedings of the American Control Conference, Seattle, Wash., pp. 3928-3932, 1995; J. A. Rossiter, et al., Feasibility and stability for constrained stable predictive control, Proceedings of the Third IEEE Conference on Control Applications, Glasgow, UK, pp. 1885-1890, 1994).
With these techniques, however, the control objective is typically regulation or tracking (but not optimizing resource allocations), and the optimization technique is only applied to control performance indexes (e.g., minimize a tracking error).
Several related patents have been issued which disclose methods for constrained optimization of dynamic systems. For instance, U.S. Pat. No. 5,381,361, entitled: Method and Apparatus for Real-Time Constraint Solution, describes conducting gradient descent techniques with analog VLSI so that the constraint solution can be performed continually in real time without the limitations of discrete optimization as implemented using digital processing. Moreover, U.S. Pat. No. 5,761,381, entitled: Computer System Using Genetic Optimization Techniques, describes methods for integrating genetic and other optimization techniques, which include genetic, simulated annealing, constraint logic, and neural networks and are interacted for synergy solutions.
However, it is believed that the known control solutions have not addressed the challenges of handling dynamics of constrained optimization systems.